/*
    数位dp-下

    前置知识: 
    讲解003、030、031、032、033 - 位运算基础
    讲解066、067、068、069 - 动态规划基础
    讲解084 - 数位dp-上
    【必备】课程的动态规划大专题从讲解066开始，建议从头开始学习会比较系统

    数位dp的尝试方式并不特殊，绝大多数都是线性展开，类似从左往右的尝试
    之前的课已经讲过 大量在数组上进行线性展开的题目，数位dp是在数字的每一位上进行线性展开而已
    不同的题目有不同的限制，解题核心在于：可能性的整理、排列组合的相关知识

    解决数位dp的问题 推荐使用记忆化搜索的方式，可能性的展开会很好写，不必刻意追求进一步改写
    递归写出来问题就解决了，位数多就挂缓存，位数不多甚至不挂缓存也能通过

    数位dp分为上、下节，本节为下期，继续讲解4个题目，来见识更多数位dp问题

    ================================================

    题目1
    windy数
    不含前导零且相邻两个数字之差至少为2的正整数被称为windy数
    windy想知道[a,b]范围上总共有多少个windy数
    测试链接 : https://www.luogu.com.cn/problem/P2657

    ================================================

    题目2
    萌数
    如果一个数字，存在长度至少为2的回文子串，那么这种数字被称为萌数
    比如101、110、111、1234321、45568
    求[l,r]范围上，有多少个萌数
    由于答案可能很大，所以输出答案对1000000007求余
    测试链接 : https://www.luogu.com.cn/problem/P3413

    ================================================

    题目3
    不含连续1的非负整数
    给定一个正整数n，请你统计在[0, n]范围的非负整数中
    有多少个整数的二进制表示中不存在连续的1
    测试链接 : 
    https://leetcode.cn/problems/non-negative-integers-without-consecutive-ones/

    ================================================

    题目4
    范围内的数字计数
    给定两个正整数a和b，求在[a,b]范围上的所有整数中
    某个数码d出现了多少次
    1 <= a, b
    测试链接 : https://leetcode.cn/problems/digit-count-in-range/
    测试链接 : https://www.luogu.com.cn/problem/P2602
    测试链接 : https://leetcode.cn/problems/number-of-digit-one/
    测试链接 : https://leetcode.cn/problems/number-of-2s-in-range-lcci/

*/